#ifndef HEAPSORT_H_
#define HEAPSORT_H_

#define PARENT(i)  (i/2)
#define LeftChild(i)    (i*2)
#define RightChild(i)   (i*2+1)

static void AdjustHeap(int arr[], int length, int node);
static void BuildHeap(int arr[], int length);
void HeapSort(int arr[], int length);

static void AdjustHeap(int arr[], int length, int node)
{
	int leftChildNode = LeftChild(node);
	int rightChildNode = RightChild(node);
	int parentNode = node;

	while(leftChildNode < length || rightChildNode < length)
	{
		parentNode = (leftChildNode < length && arr[parentNode] < arr[leftChildNode]) ? leftChildNode : parentNode;
		parentNode = (rightChildNode < length && arr[parentNode] < arr[rightChildNode]) ? rightChildNode : parentNode;
		if(node != parentNode)
		{
			int tempData = arr[parentNode];
			arr[parentNode] = arr[node];
			arr[node] = tempData;
			node = parentNode;
			leftChildNode = LeftChild(node);
			rightChildNode = RightChild(node);
		}
		else
		{
			break;
		}
	}
}

static void BuildHeap(int arr[], int length)
{
	for(int node = length / 2; node >= 0; --node)
	{
		AdjustHeap(arr, length, node);
	}
}

void HeapSort(int arr[], int length)
{
	BuildHeap(arr, length);
	int arrLength = length;
	while(arrLength > 1)
	{
		int tempData = arr[arrLength - 1];
		arr[arrLength - 1] = arr[0];
		arr[0] = tempData;
		--arrLength;
		AdjustHeap(arr, arrLength, 0);
	}
}

#endif